package com.rong.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 
 * @desc 插入排序
 * 
 *       将一个记录插入到已排好序的序列中，从而得到一个新的有序序列
 *
 * @author liurong
 *
 * @date 2020年6月29日
 */
public class InsertSort {
	public static void main(String[] args) {
//		int[] sourceArr = new int[] { 1, 5, 12, 24, 35, 66, 100 };
		int[] sourceArr = new int[] { 12, 24, 5, 35, 1, 66, 100 };
		sort(sourceArr);
		System.out.println(Arrays.toString(sourceArr));

		sourceArr = new int[1000000];
		for (int i = 0; i < 1000000; i++) {
			sourceArr[i] = new Random().nextInt(1000000);
		}

		long start = System.currentTimeMillis();
		sort(sourceArr);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

	public static void sort(int[] arr) {
		int temp = 0;
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > arr[i - 1]) {
				continue;
			}
			temp = arr[i];
			for (int j = i; j >= 0; j--) {
				if (j > 0 && temp < arr[j - 1]) {
					arr[j] = arr[j - 1];
				} else {
					arr[j] = temp;
					break;
				}
			}
		}
	}
}
